import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标
 */
public class Test55 {
    public static void main(String[] args) {
        int[] arr = {2,3,1,1,4};
        System.out.println(canJump(arr));
    }


    // 动态规划法：
    public static boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int[] can = new int[nums.length];
        can[0] = nums[0];
        if (can[0] == 0) return false;
        for (int i = 1; i < nums.length-1; i++) {
            if (nums[i] + i > can[i-1]){
                if (nums[i] == 0){
                    return false;
                }else{
                    can[i] = nums[i] + i;
                }
            }else{
                can[i] = can[i-1];
            }
        }
        if (can[can.length - 2] >= can.length-1){
            return true;
        }
        return false;
    }

    // 递归法
//    public static boolean canJump(int[] nums) {
//        boolean ret = can(nums,nums.length-1);
//        return ret;
//    }
//    public static boolean can(int[]arr,int targetIndex){
//        if (targetIndex == 0) return true;
//        for (int i = 0; i < targetIndex; i++) {
//            if (arr[i] >= (targetIndex - i)){
//                return can(arr,i);
//            }
//        }
//        return false;
//    }
}
